package my.jwds.p575;

public class DistributeCandies {

    public static void main(String[] args) {
        System.out.println(new DistributeCandies().distributeCandies(new int[]{3,2,2,1,3,1}));
    }
    public int distributeCandies(int[] candyType) {
        int half = candyType.length >> 1;
        int[] types = new int[1 << 13];
        int ans = 0;
        for (int type : candyType) {
            int index = type + 100_000;
            if ((types[index >> 5] & 1 << (index & 31)) == 0) {
                ans++;
                if (ans == half) {
                    return ans;
                }
            }
            types[index >> 5] |= 1 << (index & 31);
        }
        return ans;
    }
}
